#include <stdio.h>
#include <stdlib.h>

typedef struct LNode{
	int data;			//数据域 
	struct LNode *next;		//指针域 
}LNode,*LinkList;
 
 //有头结点的头插法建立单链表：
 LinkList List_HeadInsert(LinkList &L){
 	LNode *s;int x;
 	L=(LinkList)malloc(sizeof(LNode));	
 	L->next=NULL;
 	scanf("%d",x);
 	while(x!=-1)
 	{
 		s=(LNode*)malloc(sizeof(LNode));
 		s->data=x;
 		s->next=L->next;
 		L->next=s;
 		scanf("%d",x);
	 }
	 return L;
	  } 
	  

//有头结点的尾插法建立单链表：
LinkList List_TailInsert(LinkList &L){
	LNode *s,*r;int x;
	L=(LinkList)malloc(sizeof(LNode));
	L->next=NULL;
	r=L;
	scanf("%d",x);
	while(x!=-1){
		s=(LNode*)malloc(sizeof(LNode));
		s->data=x;
		s->next=r->next;
		r->next=s;
		r=s;
		scanf("%d",x);
	}
	
	return L;
	
}    

//按序号查找结点值
LNode *GetElem(LinkList L,int i){
	if(i=0){
		return L;
	}
	if(i<0){
		return NULL;
	}
	int j=1;
	LNode *p=L->next;
	while(j<i&&p){
		p=p->next;
		j++;
	}
	return p;
	
} 
//按值查找结点
LNode *LocateElem(LinkList L,int e){
	LNode *p=L->next;
	while(p&&p->data!=e){
		p=p->next;
	}
	return p;
	}
	
// 插入结点操作(后插)(找到第i-1个结点 
LinkList Insert1(LinkList L,int i,int e){
	LNode *p,*s;
	s=(LNode*)malloc(sizeof(LNode));
	p=GetElem(L,i-1);
	s->next=p->next;
	p->next=s;
	s->data=e;
	return L;
}
// 插入结点操作（前插）
LinkList Insert2(LinkList L,int i,int e){
	LNode *p,*s;
	p=GetElem(L,i-1);
	s=(LNode*)malloc(sizeof(LNode));
	s->data=e;
	s->next=p->next;
	p->next=s;
	int temp=p->data;
	p->data=s->data;
	s->data=temp; 
	return L;
}
//删除结点操作
LinkList Delete(LinkList &L,int i){
	LNode *p,*q;
	p=GetElem(L,i-1);
	q=p->next;
	p->next=q->next;
	free(q);
}
 

//已知单链表L，如何实现逆置？
LinkList Inverse(LinkList L){
	LinkList L1;
	L1=(LinkList)malloc(sizeof(LNode));
	L1->next=NULL;
	LNode *s,*t;
	int x;
	t=L;
	while(t->next){
		t=t->next;
		x=t->data;
		s=(LNode*)malloc(sizeof(LNode));
 		s->data=x;
 		s->next=L1->next;
 		L1->next=s;
	}
	
	return L1;
} 
